home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / news / inn1.000 / inn1.4sec-linux-src.tar / inn / lib / malloc.c < prev    next >
C/C++ Source or Header  |  1991-11-27  |  11KB  |  408 lines
  1. /* $Revision: 1.3 $
  2.  *
  3.  * Revision 4.0.1.1  91/04/11  17:48:31  lwall
  4.  * patch1: Configure now figures out malloc ptr type
  5.  * 
  6.  * Revision 4.0  91/03/20  01:28:52  lwall
  7.  * 4.0 baseline.
  8.  * 
  9.  * Slightly hacked by Matthias Urlichs (urlichs@smurf.sub.org)
  10.  * to fit into INND; 91/08/28.
  11.  */
  12. #define RCHECK
  13.  
  14. #ifndef lint
  15. static char sccsid[] = "@(#)malloc.c    4.3 (Berkeley) 9/16/83";
  16.  
  17. /*
  18.  * malloc.c (Caltech) 2/21/82
  19.  * Chris Kingsley, kingsley@cit-20.
  20.  *
  21.  * This is a very fast storage allocator.  It allocates blocks of a small 
  22.  * number of different sizes, and keeps free lists of each size.  Blocks that
  23.  * don't exactly fit are passed up to the next larger size.  In this 
  24.  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  25.  * This is designed for use in a program that uses vast quantities of memory,
  26.  * but bombs when it runs out. 
  27.  */
  28.  
  29. #include <stdio.h>
  30. #include <sys/types.h>
  31. #include "configdata.h"
  32. #include "clibrary.h"
  33. #include "logging.h"
  34.  
  35. static findbucket(), morecore();
  36.  
  37. /* I don't much care whether these are defined in sys/types.h--LAW */
  38.  
  39. #define u_char unsigned char
  40. #define u_int unsigned int
  41. #define u_short unsigned short
  42.  
  43. /*
  44.  * The overhead on a block is at least 4 bytes.  When free, this space
  45.  * contains a pointer to the next free block, and the bottom two bits must
  46.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  47.  * byte is the size index.  The remaining bytes are for alignment.
  48.  * If range checking is enabled and the size of the block fits
  49.  * in two bytes, then the top two bytes hold the size of the requested block
  50.  * plus the range checking words, and the header word MINUS ONE.
  51.  */
  52. union    overhead {
  53.     union    overhead *ov_next;    /* when free */
  54. #if ALIGNBYTES > 4
  55.     double    strut;            /* alignment problems */
  56. #endif
  57.     struct {
  58.         u_char    ovu_magic;    /* magic number */
  59.         u_char    ovu_index;    /* bucket # */
  60. #ifdef RCHECK
  61.         u_short    ovu_size;    /* actual block size */
  62.         u_int    ovu_rmagic;    /* range magic number */
  63. #endif
  64.     } ovu;
  65. #define    ov_magic    ovu.ovu_magic
  66. #define    ov_index    ovu.ovu_index
  67. #define    ov_size        ovu.ovu_size
  68. #define    ov_rmagic    ovu.ovu_rmagic
  69. };
  70.  
  71. #define    MAGIC        0xff        /* magic # on accounting info */
  72. #define OLDMAGIC    0x7f        /* same after a free() */
  73. #define RMAGIC        0x55555555    /* magic # on range info */
  74. #ifdef RCHECK
  75. #define    RSLOP        sizeof (u_int)
  76. #else
  77. #define    RSLOP        0
  78. #endif
  79.  
  80. /*
  81.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  82.  * smallest allocatable block is 8 bytes.  The overhead information
  83.  * precedes the data area returned to the user.
  84.  */
  85. #define    NBUCKETS 30
  86. static    union overhead *nextf[NBUCKETS];
  87. extern    char *sbrk();
  88.  
  89. #ifdef MSTATS
  90. /*
  91.  * nmalloc[i] is the difference between the number of mallocs and frees
  92.  * for a given block size.
  93.  */
  94. static    u_int nmalloc[NBUCKETS];
  95. #include <stdio.h>
  96. #endif
  97.  
  98. #ifdef debug
  99. #define    ASSERT(p)   if (!(p)) botch("p"); else
  100. static
  101. botch(s)
  102.     char *s;
  103. {
  104.  
  105.     printf("assertion botched: %s\n", s);
  106.     abort();
  107. }
  108. #else
  109. #ifdef __STDC__
  110. #define    ASSERT(p) if(!(p)) syslog(L_FATAL, #p); else
  111. #else
  112. #define    ASSERT(p) if(!(p)) syslog(L_FATAL, "p"); else
  113. #endif
  114. #endif
  115.  
  116. POINTER
  117. malloc(nbytes)
  118.     register SIZE_T nbytes;
  119. {
  120.       register union overhead *p;
  121.       register int bucket = 0;
  122.       register unsigned shiftr;
  123.  
  124.     /*
  125.      * Convert amount of memory requested into
  126.      * closest block size stored in hash buckets
  127.      * which satisfies request.  Account for
  128.      * space used per block for accounting.
  129.      */
  130.       nbytes += sizeof (union overhead) + RSLOP;
  131.       nbytes = (nbytes + 3) &~ 3; 
  132.       shiftr = (nbytes - 1) >> 2;
  133.     /* apart from this loop, this is O(1) */
  134.       while (shiftr >>= 1)
  135.           bucket++;
  136.     /*
  137.      * If nothing in hash bucket right now,
  138.      * request more memory from the system.
  139.      */
  140.       if (nextf[bucket] == NULL)    
  141.           morecore(bucket);
  142.       if ((p = (union overhead *)nextf[bucket]) == NULL)
  143.           return (NULL);
  144.     /* remove from linked list */
  145. #ifdef RCHECK
  146.     if (*((int*)p) & (sizeof(union overhead) - 1))
  147. #ifndef I286
  148.         fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
  149. #else
  150.         fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",*((int*)p),p);
  151. #endif
  152. #endif
  153.       nextf[bucket] = p->ov_next;
  154.     p->ov_magic = MAGIC;
  155.     p->ov_index= bucket;
  156. #ifdef MSTATS
  157.       nmalloc[bucket]++;
  158. #endif
  159. #ifdef RCHECK
  160.     /*
  161.      * Record allocated size of block and
  162.      * bound space with magic numbers.
  163.      */
  164.       if (nbytes <= 0x10000)
  165.         p->ov_size = nbytes - 1;
  166.     p->ov_rmagic = RMAGIC;
  167.       *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  168. #endif
  169.       return ((char *)(p + 1));
  170. }
  171.  
  172. /*
  173.  * Allocate more memory to the indicated bucket.
  174.  */
  175. static
  176. morecore(bucket)
  177.     register int bucket;
  178. {
  179.       register union overhead *op;
  180.       register int rnu;       /* 2^rnu bytes will be requested */
  181.       register int nblks;     /* become nblks blocks of the desired size */
  182.     register int siz;
  183.  
  184.       if (nextf[bucket])
  185.           return;
  186.     /*
  187.      * Insure memory is allocated
  188.      * on a page boundary.  Should
  189.      * make getpageize call?
  190.      */
  191.       op = (union overhead *)sbrk(0);
  192. #ifndef I286
  193.       if ((int)op & 0x3ff)
  194.           (void)sbrk(1024 - ((int)op & 0x3ff));
  195. #else
  196.     /* The sbrk(0) call on the I286 always returns the next segment */
  197. #endif
  198.  
  199. #ifndef I286
  200.     /* take 2k unless the block is bigger than that */
  201.       rnu = (bucket <= 8) ? 11 : bucket + 3;
  202. #else
  203.     /* take 16k unless the block is bigger than that 
  204.        (80286s like large segments!)        */
  205.       rnu = (bucket <= 11) ? 14 : bucket + 3;
  206. #endif
  207.       nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
  208.       if (rnu < bucket)
  209.         rnu = bucket;
  210.     op = (union overhead *)sbrk(1 << rnu);
  211.     /* no more room! */
  212.       if ((int)op == -1)
  213.           return;
  214.     /*
  215.      * Round up to minimum allocation size boundary
  216.      * and deduct from block count to reflect.
  217.      */
  218. #ifndef I286
  219.       if ((int)op & 7) {
  220.           op = (union overhead *)(((int)op + 8) &~ 7);
  221.           nblks--;
  222.       }
  223. #else
  224.     /* Again, this should always be ok on an 80286 */
  225. #endif
  226.     /*
  227.      * Add new memory allocated to that on
  228.      * free list for this hash bucket.
  229.      */
  230.       nextf[bucket] = op;
  231.       siz = 1 << (bucket + 3);
  232.       while (--nblks > 0) {
  233.         op->ov_next = (union overhead *)((caddr_t)op + siz);
  234.         op = (union overhead *)((caddr_t)op + siz);
  235.       }
  236. }
  237.  
  238. FREEVAL
  239. free(cp)
  240.     POINTER cp;
  241. {   
  242.       register int size;
  243.     register union overhead *op;
  244.  
  245.       if (cp == NULL)
  246.           return;
  247.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  248. #ifdef debug
  249.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  250. #else
  251.     if (op->ov_magic != MAGIC) {
  252.         syslog(L_ERROR, "%s free() ignored",
  253.             op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
  254.         return;                /* sanity */
  255.     }
  256.     op->ov_magic = OLDMAGIC;
  257. #endif
  258. #ifdef RCHECK
  259.       ASSERT(op->ov_rmagic == RMAGIC);
  260.     if (op->ov_index <= 13)
  261.         ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
  262. #endif
  263.       ASSERT(op->ov_index < NBUCKETS);
  264.       size = op->ov_index;
  265.     op->ov_next = nextf[size];
  266.       nextf[size] = op;
  267. #ifdef MSTATS
  268.       nmalloc[size]--;
  269. #endif
  270. }
  271.  
  272. /*
  273.  * When a program attempts "storage compaction" as mentioned in the
  274.  * old malloc man page, it realloc's an already freed block.  Usually
  275.  * this is the last block it freed; occasionally it might be farther
  276.  * back.  We have to search all the free lists for the block in order
  277.  * to determine its bucket: 1st we make one pass thru the lists
  278.  * checking only the first block in each; if that fails we search
  279.  * ``reall_srchlen'' blocks in each list for a match (the variable
  280.  * is extern so the caller can modify it).  If that fails we just copy
  281.  * however many bytes was given to realloc() and hope it's not huge.
  282.  */
  283. int reall_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  284.  
  285. POINTER
  286. realloc(cp, nbytes)
  287.     POINTER cp; 
  288.     SIZE_T nbytes;
  289. {   
  290.       register u_int onb;
  291.     union overhead *op;
  292.       char *res;
  293.     register int i;
  294.     int was_alloced = 0;
  295.  
  296.       if (cp == NULL)
  297.           return (malloc(nbytes));
  298.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  299.     if (op->ov_magic == MAGIC) {
  300.         was_alloced++;
  301.         i = op->ov_index;
  302.     } else {
  303.         /*
  304.          * Already free, doing "compaction".
  305.          *
  306.          * Search for the old block of memory on the
  307.          * free list.  First, check the most common
  308.          * case (last element free'd), then (this failing)
  309.          * the last ``reall_srchlen'' items free'd.
  310.          * If all lookups fail, then assume the size of
  311.          * the memory block being realloc'd is the
  312.          * smallest possible.
  313.          */
  314.         if ((i = findbucket(op, 1)) < 0 &&
  315.             (i = findbucket(op, reall_srchlen)) < 0)
  316.             i = 0;
  317.     }
  318.     onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
  319.     /* avoid the copy if same size block */
  320.     if (was_alloced &&
  321.         nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
  322. #ifdef RCHECK
  323.         /*
  324.          * Record new allocated size of block and
  325.          * bound space with magic numbers.
  326.          */
  327.         if (op->ov_index <= 13) {
  328.             /*
  329.              * Convert amount of memory requested into
  330.              * closest block size stored in hash buckets
  331.              * which satisfies request.  Account for
  332.              * space used per block for accounting.
  333.              */
  334.             nbytes += sizeof (union overhead) + RSLOP;
  335.             nbytes = (nbytes + 3) &~ 3; 
  336.             op->ov_size = nbytes - 1;
  337.             *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
  338.         }
  339. #endif
  340.         return(cp);
  341.     }
  342.       if ((res = malloc(nbytes)) == NULL)
  343.           return (NULL);
  344.       if (cp != res)            /* common optimization */
  345.         (void)bcopy(cp, res, (int)((nbytes < onb) ? nbytes : onb));
  346.       if (was_alloced)
  347.         free(cp);
  348.       return (res);
  349. }
  350.  
  351. /*
  352.  * Search ``srchlen'' elements of each free list for a block whose
  353.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  354.  * Return bucket number, or -1 if not found.
  355.  */
  356. static
  357. findbucket(freep, srchlen)
  358.     union overhead *freep;
  359.     int srchlen;
  360. {
  361.     register union overhead *p;
  362.     register int i, j;
  363.  
  364.     for (i = 0; i < NBUCKETS; i++) {
  365.         j = 0;
  366.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  367.             if (p == freep)
  368.                 return (i);
  369.             j++;
  370.         }
  371.     }
  372.     return (-1);
  373. }
  374.  
  375. #ifdef MSTATS
  376. /*
  377.  * mstats - print out statistics about malloc
  378.  * 
  379.  * Prints two lines of numbers, one showing the length of the free list
  380.  * for each size category, the second showing the number of mallocs -
  381.  * frees for each size category.
  382.  */
  383. mstats(s)
  384.     char *s;
  385. {
  386.       register int i, j;
  387.       register union overhead *p;
  388.       int totfree = 0,
  389.       totused = 0;
  390.  
  391.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  392.       for (i = 0; i < NBUCKETS; i++) {
  393.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  394.               ;
  395.           fprintf(stderr, " %d", j);
  396.           totfree += j * (1 << (i + 3));
  397.       }
  398.       fprintf(stderr, "\nused:\t");
  399.       for (i = 0; i < NBUCKETS; i++) {
  400.           fprintf(stderr, " %d", nmalloc[i]);
  401.           totused += nmalloc[i] * (1 << (i + 3));
  402.       }
  403.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  404.         totused, totfree);
  405. }
  406. #endif
  407. #endif /* lint */
  408.